Proof systems

(updated )

This post is a reframing of the evolution of proof systems from the contemporary perspective of LDE polynomial commitment protocols.

While proof systems have thus far always been presented end-to-end, they often break down into two parts: an arithmetization technique and a polynomial commitment scheme. Despite being presented integral, these are mostly interchangeable and it is perfectly reasonable to for example use Plonk arithmetization on the FRI commitment protocol.

flowchart LR; pr([Claim]) subgraph Arithmetization Pinocchio Groth16 Sonic Marlin Plonk Stark end pr --> Pinocchio --> lp pr --> Groth16 --> lp pr --> Sonic --> lp pr --> Marlin --> lp pr --> Plonk --> lp pr --> Stark --> lp lp([Polynomial\ncommitment\nprotocol]) subgraph "Scheme" KZG IPA FRI DARK end lp --> KZG --> fs lp --> IPA --> fs lp --> FRI --> fs lp --> DARK --> fs fs[Fiat-Shamir] --> nip([Proof])

The choice of Polynomial Commitment scheme determines the field $\F$ that is used in the arithmetization layer. While it is possible to use math outside of $\F$ in the claim, this requires costly emulation using $\F$-math. Much research has been devoted to making this emulation more efficient.

Basic Architecture

Claims

Arithmetization

Polynomial Commitment Protocols

Commitment Schemes

Interactive proofs

Fiat-Shamir

Non-interactive proofs.

Arithmetization

Pinocchio

This is the system used by Circom, Zorkates, Groth16 and most Ethereum projects that do not develop their own proof system.

The computation is first reduced to an algebraic circuit of basic operations over a field. The circuit is represented by a triplet of matrices $(A, B, C) ∈ \F^{n × m}$ such that a valid witness $\vec s ∈ \F^n$ satisfies.

$n$ is the number of variables in the system, $m$ is the number of gate relationships.

$$ \vec s ⋅ A \circ \vec s ⋅ B - \vec s ⋅ C = 0 $$

We pick a basis $\vec x ∈ \F^m$ and compute $3⋅n + 1$ polynomials $A_i, B_i, C_i, Z ∈ \F[X_{<m}]$ such that

$$ \begin{aligned} A_i(x_j) &= A_{ij} & B_i(x_j) &= B_{ij} & C_i(x_j) &= C_{ij} & Z(x_i) &= 0 \end{aligned} $$

Given a witness $\vec s$, we then compute $A, B, C ∈ \F[X_{<m}]$ such that

$$ \begin{aligned} A(X) &= \sum_i s_i ⋅A_i(X) & B(X) &= \sum_i s_i ⋅B_i(X) & C(X) &= \sum_i s_i ⋅C_i(X) \end{aligned} $$

The circuit is satisfied iff there exists a $H ∈ \F[X_{<m}]$ such that

$$ A(X) ⋅ B(X) - C(X) = H(X) ⋅ Z(X) $$

Groth16

Sonic

Stark

Plonk

Polynomial Commitment

https://hackernoon.com/kzg10-ipa-fri-and-darks-analysis-of-polynomial-commitment-schemes

KZG

We want to proof

$$ \forall_i F(x_i) = 0 $$

on some domain $\vec x ∈ \F^n$. We construct the unique $Z(X) ∈ \F[X_{<n}]$ such that $Z(x_i) = 0$.

$$ F(X) = 0 $$

Pick a random $z ∈ \F$.

https://www.cryptologie.net/article/526/maller-optimization-to-reduce-proof-size/

https://cryptologie.net/article/525/pairing-based-polynomial-commitments-and-kate-polynomial-commitments/

IPA

FRI

DARK

Implementations

https://minaprotocol.com/blog/kimchi-the-latest-update-to-minas-proof-system

https://eprint.iacr.org/2016/116

https://eprint.iacr.org/2018/828

https://cryptologie.net/article/527/understanding-plonk/

https://www.di.ens.fr/~nitulesc/files/Survey-SNARKs.pdf

Remco Bloemen
Math & Engineering
https://2π.com